package com.year_23.april;

/**
 * @author: jsh
 * @create: 2023/4/23 21:49
 * @Description:    1163. 按字典序排在最后的子串
 *                  https://leetcode.cn/problems/last-substring-in-lexicographical-order/
 * @FileName: Day24
 * @History:
 * @自定义内容：
 */
public class Day24 {
    public static void main(String[] args) {
        System.out.println('a' >= 'a');
        System.out.println(lastSubstring("leszetzcodez"));
        System.out.println(lastSubstring2("leszetzcodez"));
    }
    public static String lastSubstring2(String s) {
        int l = s.length();
        int i = 1, res = 0;
        while (i < l){
            int k = 0;
            while (i+k<l && s.charAt(res+k) == s.charAt(i +k)){
                k++;
            }
            if (i+k<l && s.charAt(res+k) < s.charAt(i + k)){
                int t = res;
                res = i;
                i = Math.max(i+1,t+k+1);

            }else {
                i = i+ k+1;
            }


        }
        return s.substring(res);
    }
    public static String lastSubstring(String s) {
        int left = 0;
        char max = 'a';
        int m = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c  > max){
                m = i;
                max = s.charAt(i);
            }else if (c == max){
                left = m;
                int right = i;
                while (left< s.length()&&right< s.length()&&s.charAt(left) == s.charAt(right)){
                    left++;
                    right++;
                }
                if (right<s.length() &&s.charAt(right) > s.charAt(left))
                    m = i;
            }

        }
        return s.substring(m);
    }
}
